using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Linq.Dynamic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0560. 和为K的子数组")]
    public class No0560_SubarraySum : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(SubarraySum, new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 0, 55);
            Assert.TestExe(SubarraySum, new int[] { 1, 2, 3, 3, 0, 3, 4, 2 }, 6, 5);
            Assert.TestExe(SubarraySum, new int[] { 1, 1, 1 }, 2, 2);
            Assert.TestExe(SubarraySum, new int[] { 1, 2, 3, 4, 6, 2, 2, 2, 3, 1 }, 4, 4);
        }

        public int SubarraySum(int[] nums, int k)
        {
            Dictionary<int, int> d = new Dictionary<int, int>();
            int acc = 0, count = 0;
            foreach (int num in nums)
            {
                acc += num;
                if (acc == k)
                {
                    count += 1;
                }

                int cindex = acc - k;
                if (d.ContainsKey(cindex))
                {
                    count += d[cindex];
                }

                if (d.ContainsKey(acc))
                {
                    d[acc] += 1;
                }
                else
                {
                    d[acc] = 1;
                }
            }
            return count;
        }
    }
}
